------- <br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011) <br />------- <br />Workshop on Metric embeddings, algorithms and hardness of approximation <br />January 17-21, 2011 <br />------- <br />Jan 18, 15:00-16:00 <br />Ryan O'Donnell (Carnegie Mellon U.) <br />Inapproximability: A How-To Guide 2 <br />------- <br />In this mini-course, I will introduce the area of approximability of <br />optimization problems and then discuss the methods used to prove <br />inapproximability results. We will assume the hardness of Label-Cover <br />and Unique-Games - these problems will be discussed in other <br />mini-courses. <br /> <br />Key tools include the discrete Fourier transform and the notion of <br />"influences" for Boolean functions. As case studies, we will discuss <br />the Max-k-Coverage, Max-3Lin, and Max-Cut problems.
